\clearpage
\item \points{20} {\bf K-means for compression}

In this problem, we will apply the K-means algorithm to lossy image
compression, by reducing the number of colors used in an image.

We will be using the files \texttt{data/peppers-small.tiff} and \texttt{data/peppers-large.tiff}.
	

The \texttt{peppers-large.tiff} file contains
a 512x512 image of peppers represented in 24-bit color. This means
that, for each of the 262144 pixels in the image, there are three
8-bit numbers (each ranging from 0 to 255) that represent the red,
green, and blue intensity values for that pixel. The straightforward
representation of this image therefore takes about $262144 \times 3 =
786432$ bytes (a byte being 8 bits). To compress the image, we will
use K-means to reduce the image to $k = 16$ colors. More specifically,
each pixel in the image is considered a point in the three-dimensional
$(r, g, b)$-space. To compress the image, we will cluster these points
in color-space into 16 clusters, and replace each pixel with the
closest cluster centroid.

Follow the instructions below. Be warned that some of these operations
can take a while (several minutes even on a fast computer)!


\begin{enumerate}

  \input{05-k_means/01-k_means_impl}

  \input{05-k_means/02-compression_factor}

\end{enumerate}

